import java.util.*;

public class test {
    //leetcode 409.最长回文串
    class Solution {
        public int longestPalindrome(String s) {
            HashMap<Character, Integer> map = new HashMap<Character, Integer>();
            int n1 = 0;
            int n2 = 0;
            for(int i = 0;i < s.length();i++) {
                char c = s.charAt(i);
                int num = map.getOrDefault(c, 0);
                map.put(c, num + 1);
            }
            for(Map.Entry<Character, Integer> m : map.entrySet()) {
                int count = m.getValue();
                if(count % 2 == 0) {
                    n1 += count;
                }else {
                    n1 += count - 1;
                    n2 = 1;
                }
            }
            return n1 + n2;
        }
    }
    //蓝桥杯 单调栈
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt(); // 读取序列的长度
        int[] arr = new int[n]; // 创建数组来存储序列
        for (int i = 0; i < n; i++) {
            arr[i] = in.nextInt(); // 读取序列中的每个元素
        }

        // 初始化四个数组，分别存储每个元素的左边第一个较大、右边第一个较大、
        // 左边第一个较小、右边第一个较小的元素
        int[] leftGreater = new int[n];
        int[] rightGreater = new int[n];
        int[] leftSmaller = new int[n];
        int[] rightSmaller = new int[n];
        Arrays.fill(leftGreater, -1);
        Arrays.fill(rightGreater, -1);
        Arrays.fill(leftSmaller, -1);
        Arrays.fill(rightSmaller, -1);

        Deque<Integer> stack = new ArrayDeque<>(); // 使用双端队列作为单调栈

        // 找到每个元素左侧的第一个较大元素
        for (int i = 0; i < n; i++) {
            // 当栈不为空且栈顶元素小于等于当前元素时，弹出栈顶元素
            // 这样可以保证栈中的元素是单调递减的
            while (!stack.isEmpty() && arr[stack.peek()] <= arr[i]) {
                stack.pop();
            }
            // 如果栈不为空，说明栈顶元素是当前元素左侧的第一个较大元素
            if (!stack.isEmpty()) {
                leftGreater[i] = arr[stack.peek()];
            }
            // 将当前元素的索引压入栈中
            stack.push(i);
        }

        stack.clear(); // 清空栈，准备处理下一个任务

        // 找到每个元素右侧的第一个较大元素
        for (int i = n - 1; i >= 0; i--) {
            while (!stack.isEmpty() && arr[stack.peek()] <= arr[i]) {
                stack.pop();
            }
            // 如果栈不为空，说明栈顶元素是当前元素右侧的第一个较大元素
            if (!stack.isEmpty()) {
                rightGreater[i] = arr[stack.peek()];
            }
            // 将当前元素的索引压入栈中
            stack.push(i);
        }

        stack.clear(); // 清空栈，准备处理下一个任务

        // 找到每个元素左侧的第一个较小元素
        for (int i = 0; i < n; i++) {
            while (!stack.isEmpty() && arr[stack.peek()] >= arr[i]) {
                stack.pop();
            }
            // 如果栈不为空，说明栈顶元素是当前元素左侧的第一个较小元素
            if (!stack.isEmpty()) {
                leftSmaller[i] = arr[stack.peek()];
            }
            // 将当前元素的索引压入栈中
            stack.push(i);
        }

        stack.clear(); // 清空栈，准备处理下一个任务

        // 找到每个元素右侧的第一个较小元素
        for (int i = n - 1; i >= 0; i--) {
            while (!stack.isEmpty() && arr[stack.peek()] >= arr[i]) {
                stack.pop();
            }
            // 如果栈不为空，说明栈顶元素是当前元素右侧的第一个较小元素
            if (!stack.isEmpty()) {
                rightSmaller[i] = arr[stack.peek()];
            }
            // 将当前元素的索引压入栈中
            stack.push(i);
        }

        // 输出结果
        display(leftGreater);
        display(rightGreater);
        display(leftSmaller);
        display(rightSmaller);
    }

    public static void display(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }
}
